package day002;

import common.Utils.*;

import java.util.Arrays;

import static common.Utils.*;

public class Code01_HeapSort {


    // 某个数现在处于index位置，继续往上移动
    // index的  父节点：(i -1)/2
    public static void heapInsert(int[] arr, int index){
        while(arr[index] > arr[(index - 1) / 2]){
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    // 某个数在index位置，能否往下移动
    //
    public static void heapify(int[] arr, int index, int heapSize){
        int left = index * 2 + 1; // 左孩子下标


        while(left < heapSize){ // 只要当前节点下方有左孩子
            int right = left + 1;
            int largest = right < heapSize && arr[right] > arr[left] ?
                    right : left;// 找到左右孩子中最大值的下标

            //父节点和较大子节点比较值，谁大把下标给largest
            largest = arr[largest] > arr[index] ? largest : index;
            if(largest == index){
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void heapSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        //把数组变成成最大堆
        for(int i = 0; i < arr.length; i++){ //O(N)
            heapInsert(arr, i);      //O(logN)
        }

        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while(heapSize > 0){ //O(N)
            heapify(arr, 0, heapSize); //O(logN)
            swap(arr, 0, --heapSize);      //O(1)
        }
    }

    public static void main(String[] args) {
        int times = 50000;
        int maxValue = 100;
        int maxSize = 100;
        boolean succeed = true;

        for(int i = 0; i < times; i++){
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            heapSort(arr1);
            compareArr(arr2);
            if(!Arrays.equals(arr1, arr2)){
                succeed = false;
            }
        }

        System.out.println(succeed ? "NICE" : "Failure");

//        int arr[] = {-87, 30, 4, 8, -6, -42, -46, -7, -2, 14, -19, 0, 32, 1, 66, -1, 0, -29, -17, 65, -83, 30, 75, 15, -62, -44, 42, -52, -8, -50, 46, -25, 58, 19, -37, 77, -40, -4, -51, -21, 26, -75, -14, -35, -21, 8, 58, -74, 14, 7, 19, -33, -73, 60, -75, -27, -47, 48, 64, -50, -36, 3, 59, -63, 0, -4, -81, 19, -23, -43, 60, 25, 54, -75, -16, -45, -7, 30, -33, 0, -13, 23, -79, 11, 6, 71, -28, 87, -63, 5, 31, 22, -42, -41, 18, 1};
//        heapSort(arr);
//        printArr(arr);
    }
}
